#include <bits/stdc++.h>
using namespace std;
int knapsack(int W, int N, vector<int>& weights, vector<int>& values) {
    vector<int> dp = vector<int>(W+1,0);
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = W; j >= 1; j--) {
            if (j >= w) {
                dp[j] = max(dp[j], dp[j - w] + v);
                cout<<"dp["<<i<<"]: "<<dp[i]<<" dp["<<j<<"-"<<w<<"]+"<<v<<": "<<dp[j - w] + v<<"\n";
            }
        }
    }
//    print(dp);
    return dp[W];
}
int main()
{
    int W = 10;
    int N = 5;
    vector<int>weights = {2,2,6,5,4};
    vector<int>values = {6,3,5,4,6};
    cout<<knapsack(W,N,weights,values);
}